#pragma once
#include<iostream>
#include<vector>
using namespace std;


//闭散列
namespace CloseHash {
    enum State {
        EMPTY,
        EXIST,
        DELETE
    };

    template<class K, class V>
    struct HashData {
        pair<K, V> _kv;
        //状态/默认为空
        State _state = EMPTY;
    };


    template<class K, class V>
    class HashTable {
    public:
        bool Insert(const pair<K, V>& kv) {

            HashData<K, V>* ret = Find(kv.first);

            if (ret) {
                return false;
            }

            if (_table.size() == 0) {
                _table.resize(10);
            }
            //计算负载因子
            else if ((double)_n / (double)_table.size() > 0.7) {
                //增容
                //vector<HashData<K, V>> newtable;
                //newtable.resize(_table.size() * 2);
                //for(auto& e : _table){
                //    if(e._state == EXIST){
                //        //重新计算映射到newTable
                //        //插入逻辑
                //    }
                //}
                //_table.swap(newtable);
                HashTable<K, V> newHT;
                newHT._table.resize(_table.size() * 2);
                for (auto& e : _table) {
                    if (e._state == EXIST) {
                        newHT.Insert(e._kv);
                    }
                }
                _table.swap(newHT._table);
            }


            //计算key的映射位置
            size_t start = kv.first % _table.size();
            size_t index = start;
            //探测后面的位置 -- 线性探测/二次探测
            size_t i = 1;
            while (_table[index]._state == EXIST) {
                //线性探测
                index = start + i;
                //二次探测
                //index = start + i * i;
                index %= _table.size();
                ++i;
            }

            //这个位置是空或者删除
            _table[index]._kv = kv;
            _table[index]._state = EXIST;
            ++_n;

            return true;
        }

        HashData<K, V>* Find(const K& key) {
            if (_table.size() == 0) {
                return nullptr;
            }
            size_t start = key % _table.size();
            size_t index = start;
            size_t i = 1;
            while (_table[index]._state != EMPTY) {
                if (_table[index]._state == EXIST && _table[index]._kv.first == key) {
                    return &_table[index];
                }
                //线性探测
                index = start + i;
                //二次探测
                //index = start + i * i;
                index %= _table.size();
                ++i;
            }
            return nullptr;
        }

        bool Erase(const K& key) {
            HashData<K, V>* ret = Find(key);
            if (ret == nullptr) {
                return false;
            }
            else {
                ret->_state = DELETE;
                --_n;
                return true;
            }
            return false;
        }


    private:
        vector<HashData<K, V>> _table;
        size_t _n = 0; //存储有效数据的个数
    };
}



//开散列
namespace OpenHash {

    template<class K, class V>
    struct HashNode {
        HashNode(const pair<K, V>& kv)
            :_kv(kv)
            ,_next(nullptr)
        {}


        HashNode<K, V>* _next;
        pair<K, V> _kv;
    };


    template<class K>
    struct Hash
    {
        size_t operator()(const K& key) //返回键值key
        {
            return key;
        }
    };


    //string类型的特化
    template<>
    struct Hash<string> {
        //BKDRHash算法
        size_t operator()(const string& s) {
            size_t value = 0;
            for (auto ch : s) {
                value += ch;
                value *= 131;
            }
            return value;
        }
    };

    template <class K, class V, class HashFunc = Hash<K>>
    class HashTable {
        typedef HashNode<K, V> Node;
    public:
      
        size_t GetNextPrime(size_t prime){
            static const int PRIMECOUNT = 28;
            static const size_t primeList[PRIMECOUNT] = {
                53ul, 97ul, 193ul, 389ul, 769ul,
                1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
                49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
                1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
                50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
                1610612741ul, 3221225473ul, 4294967291ul
            };
            size_t i = 0;
            for (; i < PRIMECOUNT; ++i){
                if (primeList[i] > prime)
                    return primeList[i];
            }
            return primeList[i];
        }



        bool Insert(const pair<K, V>& kv) {
            HashFunc hf;
            if (Find(kv.first)) {
                return false;
            }

            //负载因子到1时增容
            if (_n == _table.size()) {
                vector<Node*> newtable;

                /*size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;
                newtable.resize(newSize, nullptr);*/

                newtable.resize(GetNextPrime(_table.size()));

                //遍历取旧表中结点，重新计算映射位置，挂到新表中
                for (size_t i = 0; i < _table.size(); ++i) {
                    if (_table[i]) {
                        Node* cur = _table[i];
                        while (cur) {
                            //计算key在新表中的映射位置
                            Node* next = cur->_next;
                            size_t index = hf(cur->_kv.first) % newtable.size();
                            //头插
                            cur->_next = newtable[index];
                            newtable[index] = cur;
                            cur = next;
                        }
                        _table[i] = nullptr;
                    }
                }
                _table.swap(newtable);
            }

            //计算key映射位置
            size_t index = hf(kv.first) % _table.size();
            Node* newnode = new Node(kv);

            //头插
            newnode->_next = _table[index];
            _table[index] = newnode;

            ++_n;

            return true;
        }

        Node* Find(const K& key) {
            HashFunc hf;
            if (_table.size() == 0) {
                return nullptr;
            }

            size_t index = hf(key) % _table.size();
            Node* cur = _table[index];

            while (cur) {
                if (cur->_kv.first == key) {
                    return cur;
                }
                else {
                    cur = cur->_next;
                }
            }
            return nullptr;
        }


        bool Erase(const K& key) {
            HashFunc hf;
            size_t index = hf(key) % _table.size();

            Node* cur = _table[index];
            Node* prev = nullptr;

            while (cur) {
                if (cur->_kv.first == key) {
                    if (prev == nullptr) {
                        //头删
                        _table[index] = cur->_next;                       
                    }
                    else {
                        prev->_next = cur->_next;
                    }
                    delete cur;
                    --_n;
                    return true;
                }
                else {
                    prev = cur;
                    cur = cur->_next;
                }
            }
            return false;
        }


    private:
        vector<Node*> _table;
        size_t _n;
    };

    void TestHashTable1() {
        int a[] = { 1, 5, 30, 100000, 100, 18, 15, 7 ,40, 44 };
        HashTable<int, int> ht;

        for (auto e : a) {
            ht.Insert(make_pair(e, e));
        }
        ht.Insert(make_pair(25, 25));
    }

    void TestHashTable2() {
        string a[] = { "苹果", "苹果", "苹果", "苹果", "香蕉", "苹果", "葡萄", "苹果", "苹果", "苹果", "苹果", "苹果", "香蕉" };

        OpenHash::HashTable<string, int> ht;

        for (auto str : a) {
            auto ret = ht.Find(str);

            if (ret) {
                ret->_kv.second++;
            }
            else {
                ht.Insert(make_pair(str, 1));
            }
        }
    }
}